// 中序遍历

// 输入: [1,null,2,3]
//    1
//     \
//      2
//     /
//    3
// 输出: [null, 1, 2, 3]

import {Tree} from "./base-tree.js"

let t =new Tree();
t.insert(1);
t.insert(null);
t.insert(2);
t.insert(3);
console.log(t);

// 递归算法
let recursionInorderTraversal = function(root,array =[]){
    if(root){
        recursionInorderTraversal(root.left,array )
        array.push(root.data)
        recursionInorderTraversal(root.right,array )
    }
    return array 
}
console.log(recursionInorderTraversal(t.root));

 // 迭代算法
 let iterateInorderTraversal = function(root){
    const result =[]
    const stack = []
    let current = root
    while(current || stack.length > 0){
        while(current){
            stack.push(current)
            current = current.left
        }
        // 当 current 没有时 退出while循环
        current = stack.pop()
        result.push(current.data)
        current = current.right
    }
    return result
 }
 console.log(iterateInorderTraversal(t.root));

//   while语句 示例：

//    let n = 0;
//     while (n < 3) {
//     n++;
//     }
//    console.log(n);
// expected output: 3